/*

  Dynamic Memory Allocator Implementation
  Ben Marks, December 2013

  This program implements the functionality of malloc, free, realloc,
  and calloc. It uses segregated explicit free lists and a first-fit
  policy to maximize space efficiency and throughput.

  See the separate Implementation_Details document for details about
  design choices, debugging, and compile time constants.

 */


////////////////////////////////////////////////////////////
/*             Included Headers and Libraries             */
////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"



////////////////////////////////////////////////////////////
/*             Compile Time Constants                     */
////////////////////////////////////////////////////////////

/* Check the integrity of the heap after every operation, and
    perform other error checking during each operation. Does not
    produce output 
 
    Default: Not defined
 */
//#define DEBUG

/* Output useful debugging information and heap status summaries after
    every operation
 
    Default: Not defined
 */
//#define VERBOSE

/* Number of free lists to use. List cutoffs increase 
   by powers of two, starting at 8 bytes 
 
    Default: 15
 */
#define NUMLISTS 15

/* Initial size for the heap. 
 
    Default: 512
 */
#define STARTSIZE 512

////////////////////////////////////////////////////////////
/*     Probably Don't Want to Modify These                */
////////////////////////////////////////////////////////////

/* double word (8) alignment */
#define ALIGNMENT 8

/*
  Should the payload come from the beginning or the end of a free
  block that is being split? For best performance with reallocation, 
  the payload should come from the end of the free block. 
  (So, ALLOC_END should be #defined.)
*/
#define ALLOC_END

#ifdef VERBOSE
    #ifndef DEBUG
        #define DEBUG
    #endif
#endif

#ifdef DEBUG
  #define MEMCHECK(void) ( mm_check(void) )
#else
  #define MEMCHECK(void) 
#endif


////////////////////////////////////////////////////////////
/*                 Global Variables                       */
////////////////////////////////////////////////////////////

#ifdef VERBOSE
/* Number of operations done so far */
int numReqs;
#endif


////////////////////////////////////////////////////////////
/*             Function Preprocessor Macros               */
////////////////////////////////////////////////////////////

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)

/* Returns true if p is ALIGNMENT-byte aligned */
#define IS_ALIGNED(p)  ((((unsigned int)(p)) % ALIGNMENT) == 0)

/* How big are pointers on this system */
#define SIZE_T_SIZE (sizeof(void*))

/* Extract a value from a pointer as a void * or as an int
   (keep gcc happy and warning free) */
#define GET( ptr ) ( *(void**)(ptr) ) 
#define GETI( ptr ) ( *(int*)(ptr) )

/* Set the value at a pointer as a void * or as an int 
   (keep gcc happy and warning free) */
#define SET( ptr, value ) ( (*(int*)  (ptr)) = (value) )
#define SETP( ptr, value ) ( (*(void**)(ptr)) = (value) )

/* Extract the size from a header / footer of a block */
#define GETSIZE(block) ((*(int*)(block)) & 0xfffffff8)

/* Check if a block is free or not */
#define ISFREE(block) ( (*(int*)(block)) & 1)

/* Get the prior and next blocks in the explicit free list */
#define GETNEXT( block )  ( (*(void**)((block)+2*SIZE_T_SIZE)) )
#define GETPREV( block ) ( (*(void**)((block)+SIZE_T_SIZE)) )

/* Get the header, given payload */
#define GETHEADER( payload ) ( (payload) + SIZE_T_SIZE )

/* Get opposite boundary given one - header from footer or vv */
#define HEADERFROMFOOTER( footer ) ( (footer) - SIZE_T_SIZE - GETSIZE(footer) )
#define FOOTERFROMHEADER( header ) ( (header) + SIZE_T_SIZE + GETSIZE(header) )

/* Get neighboring block's headers */
#define GETPREVHEADER(block) (( HEADERFROMFOOTER( (block) - SIZE_T_SIZE ) ) )
#define GETNEXTHEADER(block) (( FOOTERFROMHEADER( (block) ) + SIZE_T_SIZE ) )

/* Manipulate the free list, and set values */
#define SETNEXT(block, next) ((*(void**)((block)+2*SIZE_T_SIZE))=(next))
#define SETPREV(block, prev) ((*(void**)((block)+SIZE_T_SIZE))=(prev))




////////////////////////////////////////////////////////////
/*                 Function Declarations                  */
////////////////////////////////////////////////////////////

// Interface functions
int mm_init(void);
void * mm_malloc(size_t size) ;
void * mm_calloc(size_t size );
void   mm_free(void *ptr);
void * mm_realloc(void *ptr, size_t size) ;

// Internal helper functions
static void * getFreeList( size_t newSize );
static void * getSizedPayload( size_t newSize );
static int    roundToTwo( size_t size ) ;
static void   removeFromList( void * block );
#ifndef ALLOC_END
static void * allocateBlockBegin( size_t size, void * block );
#else
static void * allocateBlockEnd( size_t size, void * block ) ;
#endif
static void * coalesceBlock( void * block );
static void   insertFreeBlock( void * block );

// Debugging Functions
#ifdef DEBUG
static int mm_check();
static int checkFreeList( void * ls );
static int checkInList ( void * blockPtr ) ;
static int checkBlockIntegrity () ;
static int checkFreeListIntegrity () ;
#endif





////////////////////////////////////////////////////////////
/*                  Function Definitions                  */
////////////////////////////////////////////////////////////



/*
 mm_init - Initializes the segregated free lists and the heap overall.
 
 The boundaries of the heap are denoted by allocated blocks. The starting block
 contains the segregated free lists. The ending block only contains a header.
 
 {      Segregated Free Lists    }
 ________________________________________________________________________
 |XXX| H | L8 | L16 | L32 | ... | L 2^k | F | H |   Free Space  | F | H |
 ^    ^----- Header              Footer --^   ^           ^       ^   ^
 |    	        Header for Free Payload ----- |           |       |   |
 |--- Unused 4 bytes 		      Free Space Payload |       |   |
                           End of (any) initial free space  -----|   |
                                              End Of Heap Header ----|
 ________________________________________________________________________
 
 Each free list points to a block that is at least 2^k bytes large, where k
 is the index of the list. If no such block exists, the pointer is NULL.
 
 To assist with alignment to 8 bytes for all payloads, the first 4 bytes
 of the heap are unused.
 
 This means that all headers and footers are 4 bytes large, and 
 together a header and footer are 8 byte aligned.
 
 */
int mm_init(void) {
    
    // Get some space
    void * heap = mem_sbrk( ALIGN(STARTSIZE) );
    
    // Sanity check for the start size
    int sizeRem = STARTSIZE
    - ALIGN(NUMLISTS*SIZE_T_SIZE) // Space for free lists
    - 2*SIZE_T_SIZE  // Header and footer for free list block
    - SIZE_T_SIZE    // Unused bytes at beginning of heap
    - SIZE_T_SIZE;    // End of heap footer block
    if ( sizeRem < 0 ) {
      printf("\nError: Initial size too small. With %d free lists,", NUMLISTS);
      printf("\n       must be at least %lud bytes. ", 
          ALIGN( NUMLISTS*SIZE_T_SIZE ) + 4 * SIZE_T_SIZE);
        return -1;
    }
    
    // First 4 bytes are unused
    SETP( heap, NULL );
    
    // We have space for NUMLISTS segregated free lists
    SET ( (heap+  SIZE_T_SIZE),  ALIGN(NUMLISTS * SIZE_T_SIZE) );
    // Initialize each list
    int i;
    for (i = 0; i < NUMLISTS; i++) {
        SETP( (heap+(i+2)*SIZE_T_SIZE), NULL );
    }
    SET ((FOOTERFROMHEADER(heap+SIZE_T_SIZE)) , ALIGN(NUMLISTS*SIZE_T_SIZE) );
    
    
    // Set up headers and footers for free block with remaining space
    if ( sizeRem > 0 ) {
        sizeRem -= 2*SIZE_T_SIZE; // Space for free block header and footer
        sizeRem |= 0x01;    // Mark as free
        SET( GETNEXTHEADER( heap + SIZE_T_SIZE ),  sizeRem );
        void* footer = FOOTERFROMHEADER( GETNEXTHEADER( heap + SIZE_T_SIZE ) );
        SET(footer, sizeRem);
        if ( sizeRem > 1 ) {
            // Only add the block if it has any space in the payload
            insertFreeBlock( GETNEXTHEADER( heap + SIZE_T_SIZE ) );
        }
    }
    
    // Set the end of the heap with a phony allocated block of size 0
    SET (( mem_heap_hi() - 3 ), 0) ;
    
    MEMCHECK();
    
    return 0;
}


/*
 
 Given a size, returns a pointer to a payload of size at least size. The
 payload is guaranteed to not overlap with any other payloads. Further,
 the payload will not be modified or moved until it is explicitly freed by
 the application.
 
 Returns: A pointer to a payload of size at least size.
 
 */
void *mm_malloc(size_t size) {
    
#ifdef VERBOSE
    printf("\nMallocing size %lud", size);
    numReqs ++;
#endif
    
    if ( size <= 0 ) {
        return NULL;
    }
    
    MEMCHECK();
    
    // Fulfill alignment requirements
    int newSize = ALIGN(size);
    
    // Get a free block that is at least newSize bytes
    void * iterBlock = getSizedPayload( newSize );
    
    if ( ! iterBlock ) {
        // No such block exists - expand the heap, but don't add the new block
        // to any free lists
        int expandBy = roundToTwo( newSize );
        void * newHeader = mem_heap_hi() - SIZE_T_SIZE + 1;
        SET ( newHeader, ((expandBy - SIZE_T_SIZE) | 1) );
        mem_sbrk( expandBy );
        SET ( FOOTERFROMHEADER(newHeader), ((expandBy - SIZE_T_SIZE) | 1) );
        // Restore end of heap footer boundary block
        SET ( mem_heap_hi() - SIZE_T_SIZE + 1, 0 );
        iterBlock = newHeader;
        iterBlock = coalesceBlock( newHeader );
    }
    else {
        // We'll use this block, so take it out of the free list
        removeFromList( iterBlock );
    }
    
    void * toRet;
    
#ifdef ALLOC_END
    // Allocate payloads from the end of free blocks
    void * allocated = allocateBlockEnd( size, iterBlock );
    
    // iterBlock is (possibly) a smaller free block, which should be
    // inserted if it has non-zero size.
    if ( ISFREE( iterBlock ) && GETSIZE( iterBlock ) ) {
        insertFreeBlock( iterBlock );
    }
    
    // Return pointer to payload of block
    toRet = allocated + SIZE_T_SIZE;
#else
    // Allocate payloads from the beginning of free blocks
    void * smallerFree = allocateBlockBegin( size, iterBlock );
    
    // smallerFree is (possibly) a smaller free block, which should be
    // inserted if it has non-zero size.
    if ( smallerFree && GETSIZE(smallerFree) ) {
        insertFreeBlock( smallerFree );
    }
    
    // Return pointer to payload of block
    toRet = iterBlock + SIZE_T_SIZE;
#endif
    
    
    MEMCHECK();
    
    
    return toRet;
    
}

/*
 
 Given a size, returns a pointer to an initialized payload of all zeros
 of size at least size. The payload is guaranteed to not overlap with
 any other payloads. Further, the payload will not be modified or moved
 until it is explicitly freed by the application.
 
 Returns: A pointer to a payload of size at least size that has been
 initialized to zeros.
 
 */
void * mm_calloc(size_t size ) {
    
    void * toRet = mm_malloc( size );
    if ( ! toRet ) {
        return NULL;
    }
    // Check usage of memset
    memset ( toRet, 0, size );
    
    return toRet;
    
}


/*
 
 Given a pointer to a payload that is allocated, free that block for
 future use, coalescing it and inserting it into the appropriate free
 list.
 
 Returns: Nothing.
 
 */
void mm_free(void *ptr)
{
    
#ifdef VERBOSE
    printf("\nFreeing block %p", ptr - SIZE_T_SIZE);
    numReqs ++;
#endif
    
    MEMCHECK();
    
    
    // Set the headers to indicate the block is now free
    void * header = ptr - SIZE_T_SIZE;
    
    GETI( header ) |= 1 ;
    
    void * footer = FOOTERFROMHEADER( header );
    SET( footer, GETI( header ) );
    
    
    void * coalesce = coalesceBlock( header );
    
    // Insert the block into the free list
    insertFreeBlock( coalesce );
    
    MEMCHECK();
    
    
}

/*
 mm_realloc - Given a pointer to a previously allocated payload and a size,
 return a pointer to a payload with size at least size, where the data in
 the beginning of the block matches the contents of the original block. If
 for some reason moving fails, the contents of the original block are not
 changed.
 
 Returns: A pointer to a payload of size at least size, or NULL if an error
 occured.
 */
void *mm_realloc(void *ptr, size_t size)
{
    
    size = ALIGN( size );
    
#ifdef VERBOSE
    printf("\nReallocing %p to new size of %lud from old size of %ud", 
        ptr - SIZE_T_SIZE,
        size, GETSIZE( ptr - SIZE_T_SIZE) );
    numReqs ++;
#endif
    MEMCHECK();
    
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;
    
    if ( size == 0 ) {
        mm_free( ptr );
    }
    
    if ( ! ptr ) {
#ifdef VERBOSE
        printf("\nRealloc called with null pointer. Calling malloc.");
#endif
        return mm_malloc( size );
    }
    
    if ( size <= GETSIZE( ptr - SIZE_T_SIZE ) ) {
#ifdef VERBOSE
        printf("\nRealloc called with size leq current size.");
        printf("\nReturning pointer.");
#endif
        return ptr;
    }
    
    if ( GETNEXTHEADER( ptr - SIZE_T_SIZE ) + SIZE_T_SIZE > mem_heap_hi() ) {
#ifdef VERBOSE
        printf("\nRealloc called on block at end of heap. Extending heap.");
#endif
        int sizeNeeded = size - GETSIZE( ptr - SIZE_T_SIZE );
        sizeNeeded = ALIGN(roundToTwo( sizeNeeded ));
        mem_sbrk( sizeNeeded );
        int newSize = GETSIZE( ptr - SIZE_T_SIZE ) + sizeNeeded;
        SET( ptr - SIZE_T_SIZE, newSize );
        SET( FOOTERFROMHEADER( ptr - SIZE_T_SIZE ), newSize );
        SET( mem_heap_hi() - SIZE_T_SIZE + 1, 0);
        
#ifdef DEBUG
        assert( GETSIZE( ptr - SIZE_T_SIZE ) >= size );
#endif
        
        MEMCHECK();
        return ptr;
    }
    
    
    // Handle the realloc request by mallocing a new block, 
    // copying the data over,
    // freeing the old block, and returning the new payload.
    newptr = mm_malloc(size);
    if (newptr == NULL)
        return NULL;
    copySize = GETSIZE( ptr - SIZE_T_SIZE );
    if (size < copySize)
        copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
    
    
    
}


/*
 Given a size,returns the largest free list in which a block of that size could
 be inserted. The returned free list has as its value a pointer to a block with
 at least that size.
 
 
 Ex: Called with a size of 32, this would return a pointer to the free list
 contining blocks between 32 and 63 bytes (provided they exist).
 */
static void * getFreeList( size_t newSize ) {
    
    int incr = 8;
    void * toRet = mem_heap_lo() + 2*SIZE_T_SIZE; // 8 Byte free list
    void * freeListEnds = mem_heap_lo() + ((NUMLISTS + 1)*SIZE_T_SIZE);
    int tmp;
    // While the size is greater than the next free list, 
    // and there is a next free list
    // go to the next free list and repeat
    while ( newSize > (tmp = incr<<1) && toRet < (freeListEnds) ) {
        incr = tmp;
        toRet += SIZE_T_SIZE; // Move to next free list
    }
    
    return toRet;
    
}

/*
 Get a block with a payload of size at least newSize. With the 
 segregated free lists, the block is guaranteed to be at most 
 twice the size needed, provided such a block
 exists.
 
 If no block in the heap is large enough, then NULL is returned.
 
 Returns a pointer to the header of the block, or NULL if no such block exists.
 */
static void * getSizedPayload( size_t newSize ) {
    
    
    void * freeListEnds = mem_heap_lo() + ((NUMLISTS+1)*SIZE_T_SIZE);
    
    // If there's a block, it's in this list or a later list
    void * candidateList = getFreeList( newSize );
    // Look at all lists that may contain appropriate payloads
    while ( candidateList <= freeListEnds ) {
        // While there are still larger free lists 
        // that may contain appropriate blocks
        
        void * iter = GET( candidateList );
        if ( iter ) {
            while ( iter &&  GETSIZE( iter ) < newSize ) {
                // While there's still something in 
                // the current free list to explore
                iter = GETNEXT( iter );
            }
            if ( iter ) {
                // We found something in the free list
#ifdef DEBUG
                assert ( GETSIZE( iter ) >= newSize );
#endif
                return iter;
            }
        }
        // Go to next list
        candidateList += SIZE_T_SIZE;
    }
    
#ifdef VERBOSE
    printf("\nNo blocks of size %lud in free lists.", newSize);
#endif
    
    return NULL;
    
}

/*
 Given a free block already in a free list, remove the block from that free
 list. The block must already be in the free list.
 
 Maintain the following properties of free lists:
 - If there are any blocks in the list, then a pointer to the first block
 is stored in the first payload block of the heap.
 - The first block in the free list has a prior pointer of NULL.
 - The last block in the free list has a next pointer of NULL.
 
 */
static void removeFromList( void * block ) {
    
#ifdef DEBUG
    assert ( ISFREE( block ) );
    assert ( GETSIZE( block ) > 0);
#endif
    
    // Prior block in list should have it's next point to this block's next.
    void * priorBlock = GETPREV( block );
    void * nextBlock = GETNEXT( block );
    
    void * head = getFreeList( GETSIZE(block) );
    
    // Handle case where this block is the head of the list
    if ( NULL == priorBlock ) {
        SETP( head, nextBlock );
    }
    else {
        SETNEXT( priorBlock, nextBlock ) ;
    }
    
    // Handle case where this block is not at the end of the list
    if ( NULL != nextBlock ) {
        SETPREV( nextBlock, priorBlock );
    }
    
}

/*
 Given a size, return the smallest power of two that is larger or equal to
 than that size.
 
 Ex: roundToTwo( 32 ) returns 32
 Ex: roundToTwo( 37 ) returns 64
 */
static int roundToTwo( size_t size ) {
    
    int toRet = 1;
    while ( toRet <= size ) {
        toRet <<= 1;
    }
    return toRet;
    
}

/* Given a block and a size, allocates a smaller block of size size from
 the beginning of the larger block, returning a pointer to the header of the
 remaining free block.
 
 Returns a pointer to the header of the free block, if one exists.
 
 The returned free block is not inserted into any free lists.
 
 Ex:
 
 ___________        _______________
 |  Free   |  ==>>> | Used | Free |
 -----------        ---------------
                           ^Return Value
 
 ___________        _______________
 |  Free   |  ==>>> |    Used     |
 -----------        ---------------
 Return Value = NULL
 
 */
#ifndef ALLOC_END
static void * allocateBlockBegin( size_t size, void * block ) {
    
#ifdef DEBUG
    assert ( GETSIZE(block) >= size ) ;
    assert ( ISFREE( block ) );
#endif
    
#ifdef VERBOSE
    printf("\nAbout to allocate %lud bytes from %p", size, block);
#endif
    
    size_t blockSize = GETSIZE( block );
    size_t payloadSize = ALIGN(size);
    
    // Make a header for the allocated block
    SET(block, payloadSize);
    
    // Make the footer too
    void * allocatedFooter = FOOTERFROMHEADER ( block );
    SET(allocatedFooter, payloadSize);
    
    // Make a new header for the free block
    size_t sizeRemaining = blockSize - payloadSize;
    if ( ! sizeRemaining ) {
        return NULL;
    }
    // Space for headers, and mark block as free
    sizeRemaining -= 8;
    sizeRemaining |= 0x01;
    
    
    void * newHeader = allocatedFooter + SIZE_T_SIZE;
    
    SET(newHeader, sizeRemaining);
    void * newFooter = FOOTERFROMHEADER( newHeader );
    SET(newFooter, sizeRemaining);
    
#ifdef VERBOSE
    printf("\nSmaller Free Block:Header %p,Footer %p,HV %d FV %d,Size:%lud",
           newHeader, newFooter, GETI(newHeader), GETI(newFooter),
           sizeRemaining);
    printf("\nDone allocating.");
#endif
    
    return newHeader;
    
}
#endif


/* Given a block and a size, allocates a smaller block of size size from
 the end of the larger block, returning a pointer to the header of the
 allocated block.
 
 Returns a pointer to the beginning of the allocated block.
 
 Ex:
 ___________        _______________
 |  Free   |  ==>>> | Free | Used |
 -----------        ---------------
                           ^Return Value
 
 */
#ifdef ALLOC_END
static void * allocateBlockEnd( size_t size, void * block ) {
    
#ifdef DEBUG
    assert ( GETSIZE( block ) >= size );
    assert ( ISFREE( block ) );
#endif
    
#ifdef VERBOSE
    printf("\nAbout to allocate %lud bytes from %p", size, block);
#endif
    
    size_t blockSize = GETSIZE( block );
    size_t payloadSize = ALIGN(size);
    
    
    // Make a new header for the free block, if needed
    size_t sizeRemaining = blockSize - payloadSize;
    if ( sizeRemaining ) {
        sizeRemaining -= 8;
        sizeRemaining |= 0x01;
        
        SET(block, sizeRemaining);
        SET(FOOTERFROMHEADER(block), sizeRemaining);
        
        // And then put in the allocated block
        void * allocatedHeader = GETNEXTHEADER( block );
        SET( allocatedHeader, payloadSize );
        SET( FOOTERFROMHEADER( allocatedHeader ) , payloadSize );
        return allocatedHeader;
    }
    
    else {
        // There's no free extra space
        SET( block ,  payloadSize) ;
        SET( FOOTERFROMHEADER( block ) ,  payloadSize) ;
        return block;
    }
    
    
    // Never get here
    return NULL;
    
}

#endif

/*
 Given a free block, coalesce it with any adjacent free neighboring blocks.
 
 Returns a pointer to the new block, which may be the
 same or different depending on the status of neighboring 
 blocks. The new block is not inserted into free lists.
 
 Ex:
 
 ___________________          ______________________
 |  A  |  F  |  F  |  ==>>>   |  A   |      F      |
 -------------------          ----------------------
                                     ^--- Return Value
 
 ___________________          ______________________
 |  A  |  F  |  A  |  ==>>>   |  A   |  F  |  A    |
 -------------------          ----------------------
                                     ^--- Return Value
 
 ___________________          ______________________
 |  F  |  F  |  F  |  ==>>>   |        F           |
 -------------------          ----------------------
                              ^--- Return Value
 */

static void * coalesceBlock( void * block ) {
    
#ifdef DEBUG
    assert ( ISFREE(block) );
#endif
    
    // Get our bearings with adjacent headers
    void * previousHeader = GETPREVHEADER( block );
    void * nextHeader =     GETNEXTHEADER( block );
    
    void * currHeader = block;
    void * currFooter = nextHeader - SIZE_T_SIZE;
    
    // Coalesce with prior block if free
    if ( ISFREE( previousHeader ) ) {
        if (GETSIZE(previousHeader)){
            removeFromList( previousHeader );
        }
        // Set the previous header with updated size
        // (2*SIZE_T_SIZE from headers / footers)
        int newSize = GETSIZE( previousHeader )
          + 2*SIZE_T_SIZE + GETSIZE( block );
        newSize |= 1;
        SET( previousHeader, newSize );
        // Set the footer as well
        SET( nextHeader - SIZE_T_SIZE, newSize );
        currHeader = previousHeader;
        currFooter = nextHeader -  SIZE_T_SIZE;
    }
    
    // Coalesce with next block as well, if free
    if ( ISFREE( nextHeader ) ) {
        if ( GETSIZE(nextHeader)) {
            removeFromList( nextHeader );
        }
        int newSize = GETSIZE( currHeader )
          + 2*SIZE_T_SIZE + GETSIZE( nextHeader );
        newSize |= 1;
        SET (currHeader, newSize);
        currFooter = FOOTERFROMHEADER( currHeader );
        SET (currFooter, newSize);
    }
    
#ifdef DEBUG
    // Check that adjacent blocks are allocated
    void * prev = GETPREVHEADER( currHeader );
    void * next = GETNEXTHEADER( currHeader );
    if ( prev ) {
        assert ( ! ISFREE( prev ) );
    }
    if ( next ) {
        assert ( ! ISFREE( next ) );
    }
    
    assert( ISFREE( currHeader ) );
#endif
    
    // Returns the coalesced block
    return currHeader;
}


/*
 
 Given a pointer to the header of a free block, insert that block into the
 appropriate segregated free list. The block is inserted at the head of the
 free list. This sacrifices some utilization in favor of throughput.
 
 Returns: Nothing.
 */
static void insertFreeBlock( void * block ) {
    
    // Which free list should this go in?
    void * head = getFreeList( GETSIZE(block) );
    void * firstBlock = GET(head);
    
    // Set the next pointer in the free block
    if ( firstBlock ) {
        SETNEXT( block, firstBlock );
        SETPREV( firstBlock, block );
    }
    else {
        SETNEXT( block, NULL );
    }
    
    // Set the previous pointer in the block
    SETPREV( block, NULL ); 
    
    // Update the free list
    SETP(head,  block);
    
    
}



/* Check the integrity of the heap by performing the following checks:
 
   - Checking the integrity of all blocks in the heap
   - Checking the integrity of all blocks in free lists
   - Checking that there is a 1 : 1 correspondence between free blocks
     and blocks in the free lists.
 
 Returns 0 if test was successful, -1 otherwise if error is not fatal.
 Throws an exception for anything other than non-coalesced blocks.
 
 */
#ifdef DEBUG
static int mm_check() {
    
  // Heap status information
#ifdef VERBOSE
    printf("\n\nHEAP INFORMATION: \n\n");
    printf("\n Heap Begins at: %p", mem_heap_lo());
    printf("\n   Heap Ends at: %p", mem_heap_hi() );
#endif
    
    // Check integrity of all blocks in the heap
    int heapNonzeroFreeCount = checkBlockIntegrity() ;

    // Check integrity of all explicit free lists
    int freeListCount = checkFreeListIntegrity() ;

#ifdef VERBOSE
  printf("\nCounted %d items in free lists, and %d free blocks in the heap",
	 freeListCount, heapNonzeroFreeCount );
#endif

    // Check that the number of blocks in free lists matches the
    // number of free blocks in the heap
    assert ( freeListCount == heapNonzeroFreeCount );
    
    // Heap status information
#ifdef VERBOSE
    printf("\nProcessed Requests: %d ", numReqs);
    printf("\n--END--\n\n");
    fflush(stdout);
#endif

    // Tests successful
    return 0;
    
}

#endif

#ifdef DEBUG
  
/* 
   Checks the integrity of the free lists with the following checks:

     - All block headers and footers match
     - All blocks in free lists are actually free
     - All pointers point to valid heap addresses
     - The prior block of the next block is the current block

     Additionally, counts the number of items in all the lists.
     Returns the total number of items in the free lists.

*/    

static int checkFreeListIntegrity() {  
  
  // Check that free lists are valid
  int i;
  int listCount = 0;
  for ( i = 0; i < NUMLISTS; i++ ) {
#ifdef VERBOSE
    printf("\nFree List %5d at %p", 1 << (i + 3), 
	   mem_heap_lo() + (2+i)*(SIZE_T_SIZE) );
#endif
    checkFreeList( mem_heap_lo() + (2+i)*(SIZE_T_SIZE)  );
    
    // Count the number of items in the list
    void * ls = mem_heap_lo() + (2+i)*(SIZE_T_SIZE);
    void * iter = GET( ls );
    while ( iter ) {
      listCount ++;
      iter = GETNEXT( iter );
    }
  }
  
  return listCount;
  
  
}

#endif

#ifdef DEBUG

/* 
   Checks the integrity of all blocks on the heap, performing 
   the following checks:

   - All blocks have at least 0 size. 
   - All blocks are aligned to 8 bytes
   - Footers and headers match
   - No non-coalesced blocks

   Additionally, counts the number of free blocks with nonzero size,
   returning the total number of counted blocks.

 */
int checkBlockIntegrity () {
  
  void * begin = mem_heap_lo() + SIZE_T_SIZE;
  void * end = mem_heap_hi();
  void * iter = begin;
  int lastFree = 0;
  
  int heapNonzeroFreeCount = 0;
  
  // Verify that headers and footers are intact, blocks are contiguous, and
  // no blocks overlap
  while ( iter && iter < end ) {
#ifdef VERBOSE
    printf("\nBlock at address %p:  Size: %d  %s",
	   iter, GETSIZE(iter), (ISFREE(iter) ? "FREE" : "ALLOCATED") );
#endif
    // Sanity check on size of block
    assert( GETSIZE(iter) >= 0 );
    
    // Check that the block is aligned
    assert ( IS_ALIGNED( iter + SIZE_T_SIZE ) );
    
    // Check that the footer matches the header, provided footer exists
    if ( iter + SIZE_T_SIZE + GETSIZE(iter) < end ) {
      assert( (GET(iter)) == (GET(iter + SIZE_T_SIZE + GETSIZE(iter))) );
    }

    // Check for non-coalesced free blocks
    if ( ISFREE(iter) ) {
      if ( GETSIZE( iter ) ) {
        assert ( checkInList ( iter ) );
	heapNonzeroFreeCount ++;
      }
      if ( lastFree ) {
        printf("\n*** Warning - Non-coalesced free blocks found!!");
      }
      lastFree = 1;
    }
    else {
      lastFree = 0;
    }
    iter += (2*SIZE_T_SIZE + GETSIZE(iter));
  }
  return heapNonzeroFreeCount;
}
#endif

/* Given a free list, print out all of the blocks in that list, along with
   their size. Also, verify the integrity of the free list with the following
   checks:
     - All block headers and footers match
     - All blocks in free lists are actually free
     - All pointers point to valid heap addresses
     - The prior block of the next block is the current block
   
   Returns 0 if all checks pass 
   (and terminates with assertions failing otherwise).
*/
#ifdef DEBUG
static int checkFreeList( void * ls ) {
  
  void * iter = GET(ls); 

  void * validMin = mem_heap_lo();
  void * validMax = mem_heap_hi();
  
  while ( iter ) {

#ifdef VERBOSE
    printf("\n\tBlock: %p  Size:  %d", iter, GETSIZE( iter ) );
#endif

    // Check that the footer matches the header
    assert( (GET(iter)) == (GET(iter + SIZE_T_SIZE + GETSIZE(iter))) );

    // Check that the block is actually free
    assert ( ISFREE( iter ) );

    // Check that the pointers point to valid heap addresses
    assert( iter >= validMin );
    assert( iter <= validMax );
    if ( GETNEXT(iter) ) {
      assert( GETNEXT(iter) >= validMin );
      assert( GETNEXT(iter) <= validMax );
    }
    if ( GETPREV(iter) ) {
      assert( GETPREV(iter) >= validMin );
      assert( GETPREV(iter) <= validMax );
    } 

    void * tmp = iter;
    iter = GETNEXT( iter );
    if ( iter ) {
      // Check that all prior pointers are valid
      assert ( GETPREV(iter) == tmp );
    }
  }
  return 0;
}
#endif

/*
  Check that a given block is in the appropriate free list. 

  Returns non-zero if the block is in the correct list, or 0 otherwise.
*/
#ifdef DEBUG
static int checkInList ( void * blockPtr ) {

#ifdef VERBOSE 
  printf("\nChecking that block %p is in the right free list",
	 blockPtr);
#endif

  assert ( ISFREE( blockPtr ) );
  void * candidateList = getFreeList ( GETSIZE( blockPtr ) );
  void * iter = GET ( candidateList );
  while ( iter && iter != blockPtr ) {
    iter = GETNEXT( iter );
  }
#ifdef VERBOSE
  if ( ! iter ) {
    printf(":  FAIL");
  }
  else {
    printf(":  PASS");
  }
#endif
  if ( iter ) {
    return 1;
  }
  return 0;

}
#endif





////////////////////////////////////////////////////////////
/*             Team Information For Driver                */
////////////////////////////////////////////////////////////
team_t team = {
  /* Team name */
  "bmarks1",
  /* First member's full name */
  "Ben Marks",
  /* First member's email address */
  "bmarks1@cs.swarthmore.edu",
  /* Second member's full name (leave blank if none) */
  "",
  /* Second member's email address (leave blank if none) */
  ""
};
